class Solution {
public:
    int numDecodings(string s) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
    	if (s == "") {
			return 0;
		}
		int n = s.length();
		vector<int> dp(n);

		for (int i = 0; i < n; ++i) {
			if (s[i] != '0') {
				if (i - 1 >= 0) {
					dp[i] += dp[i- 1];
				} else {
					dp[i] += 1;
				}
			}
			if (i - 1 >= 0 &&
				s[i - 1] != '0' &&
				(s[i - 1] - '0') * 10 + (s[i] - '0') <= 26) {
				if (i - 2 >= 0) {
					dp[i] += dp[i - 2];
				} else {
					dp[i] += 1;
				}
			}
		}
		return dp[n - 1];

    }
};